package huawei.dpoint;

import ListNode.ListNode;

/**
 * https://leetcode-cn.com/problems/sort-list/
 */
public class J148 {
    public static void main(String[] args){
       // System.out.println(sortList(ListNode.createListNode(4,2,1,3)).toString());
        System.out.println(sortList2(ListNode.createListNode(4,2,1,3)).toString());
    }
    public static ListNode sortList(ListNode head) {
        ListNode cat=new ListNode(-1);

        while (head!=null){
            ListNode tmp = cat;
            boolean flagAdded =false;
            while (tmp.next!=null){
                if (tmp.next.val>head.val){
                    ListNode replace =tmp.next;
                    tmp.next=head;
                    head=head.next;
                    tmp.next.next=replace;
                    flagAdded=true;
                    break;
                }
                tmp=tmp.next;
            }
            if(!flagAdded){
                tmp.next=head;
                head=head.next;
                tmp.next.next=null;
            }
        }
        return cat.next;
    }
    public static ListNode sortList2(ListNode head) {
        return sortList2(head,null);
    }
    public static ListNode sortList2(ListNode head,ListNode end) {
        if(head==null){
            return null;
        }
        if(head.next==end){
            head.next=null;
            return head;
        }
        // 找到中点
        ListNode fast =head;
        ListNode slow= head;
        while (fast!=end){
            slow=slow.next;
            fast=fast.next;
            if(fast!=end){
                fast=fast.next;
            }
        }
        ListNode mid = slow;
        return merge(sortList2(head,mid),sortList2(mid,end));

    }
    public static ListNode merge(ListNode left,ListNode right){
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (left!=null&&right!=null){
            if(left.val<right.val){
                cur.next= left;
                left=left.next;
            }else {
                cur.next=right;
                right=right.next;
            }
            cur=cur.next;
        }
        while (left!=null){
            cur.next= left;
            left=left.next;
            cur=cur.next;
        }
        while (right!=null){
            cur.next=right;
            right=right.next;
            cur=cur.next;
        }
        return head.next;
    }
}
